#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <deque>
#include <algorithm>
using namespace std;

template <class T>
class pool
{
protected:
	pool(){}
	~pool()
	{
		// leak them
		//for(size_t i=0;i<cache.size();i++)
		//	base_type::deallocate(cache[i], 1);
	}
	vector<T*> cache;

public:
	static pool& instance()
	{
		static pool inst;
		return inst;
	}
	bool empty(){ return cache.empty(); }
	T* pop() {
		if(empty())
			return NULL;
		T* p=cache.back();
		cache.pop_back();
		return p;
	}
	void push(T* p)
	{
		cache.push_back(p);
	}
};

#define __map map // map type used
template <class T>
struct myallocator : public allocator<T>
{
	typedef typename allocator<T> base_type;
	//vector<base_type::pointer> cache;

	///////////////////////////////  std behavior, useless code
	template<class _Other>
		struct rebind
		{typedef myallocator<_Other> other;};
	myallocator() _THROW0(){}
	myallocator(const myallocator<T>&) _THROW0(){}
	template<class _Other>
	myallocator(const myallocator<_Other>&) _THROW0(){}
	template<class _Other>
		myallocator<T>& operator=(const myallocator<_Other>&)
		{return (*this);}

	base_type::pointer allocate(size_type _Count)
	{
		//if(_Count==1 && !cache.empty())
		//{
		//	base_type::pointer p=cache.back();
		//	cache.pop_back();
		//	return p;
		//}

		if(_Count==1 && !pool<T>::instance().empty())
			return pool<T>::instance().pop();
		
		return base_type::allocate(_Count);
	}
	pointer allocate(size_type _Count, const void _FARQ *)
	{	// allocate array of _Count elements, ignore hint
		return (allocate(_Count));
	}
	void deallocate(pointer _Ptr, size_type _Count)
	{
		if(_Count==1)
			pool<T>::instance().push(_Ptr);
			//cache.push_back(_Ptr);
		else
			base_type::deallocate(_Ptr, _Count);
	}

	~myallocator()
	{
		//for(size_t i=0;i<cache.size();i++)
		//	base_type::deallocate(cache[i], 1);
	}
};

template<class K, class V>
struct mymap
{
	typedef typename __map<K, V, less<K>, myallocator<pair<K, V> > > map_type;
	typedef typename map_type::iterator map_type_itr;

	typedef typename list<map_type_itr, myallocator<map_type_itr> > order_type;
	typedef typename order_type::iterator order_type_itr;

	typedef typename __map<K, order_type_itr, less<K>, myallocator<pair<K, order_type_itr> > > order_itr_map_type;

	map_type data;
	order_type order;
	order_itr_map_type order_itr;

	V& operator[](const K& k)
	{
		map_type_itr it1=data.find(k);

		if(it1==data.end())
			it1=data.insert(make_pair(k, V())).first;

		// maintain reference
		order_itr_map_type::iterator pOrderItr=order_itr.find(k);
		if(pOrderItr==order_itr.end()) // order for this k hasn't been set
		{
			order.push_front(it1);
			pOrderItr= order_itr.insert(make_pair(k, order.begin())).first;
		}

		// order itr
		order_type_itr& it2=pOrderItr->second;

		if(order.begin()!=it2) // ok, perfect
		{
			if(it2!=order.end()) // already exist
				order.erase(it2);

			order.push_front(it1);
			it2=order.begin();
		}

		// whether remove the eldest visited
		if(!order.empty() && shouldRemoveEldest())
		{
			erase(order.back()->first); // erase using key
		}

		return it1->second;
	}
	int size(){ return data.size(); }
	void erase(const K k)
	{
		data.erase(k);

		order_itr_map_type::iterator it=order_itr.find(k);
		if(it!=order_itr.end())
		{
			order.erase(it->second);
			order_itr.erase(it);
		}
	}

	// output
	void output(vector<pair<K, V> >& o)
	{
		for(order_type::iterator it=order.begin(); it!=order.end();it++)
		{
			map_type_itr& it_map=*it;
			o.push_back(*it_map);
		}
	}

	static const int capacity=50;
	bool shouldRemoveEldest()
	{
		return size()>capacity;
	}
};

typedef mymap<string, int> cache_map;

typedef pair<string, int> PSI;
bool comp(const PSI& p1, const PSI& p2){ return p1.second>p2.second; }

#include <crtdbg.h>
int main()
{
	_CrtSetDbgFlag(_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG) | _CRTDBG_LEAK_CHECK_DF);
	cache_map mm1;

	char s[4]="123";
	for(int rpt=1000; rpt>0;rpt--)
	{
		s[0]=char(rand()%('z'-'a')+'a');
		s[1]=char(rand()%('z'-'a')+'a');
		s[2]=char(rand()%('z'-'a')+'a');

		if(rand()%2==0)
		{
			s[0]='a';
			if(rand()%2==0)
			{
				s[1]='a';
				if(rand()%2==0)
					s[2]='a';
			}
		}

		mm1[s]++;
	}

	vector< pair<string, int> > top;
	mm1.output(top);
	nth_element(top.begin(), top.begin()+10, top.end(), comp);
	sort(top.begin(), top.begin()+10, comp); // optional

	for(size_t i=0;i<10;i++)
		cout<< top[i].first << " "<< top[i].second <<endl;

	return 0;
}